package Tree;

import java.util.*;

public class TraversalByIteration {

    //迭代法实现二叉树前序遍历（使用栈）
    public List<Integer> preorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        stack.push(root);
        //只有栈里没有东西时，才停止循环
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            stack.pop();
            result.add(node.val);
            //注意先push右孩子，因为先进后出，前序遍历是前中后，右孩子是后
            if(node.right != null) {
                stack.push(node.right);
            } else if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    //迭代法实现二叉树后序遍历（使用栈）
    //前序遍历是中左右，后序是左右中，因此可以将前序遍历代码复用，修改一下顺序
    //中左右 --> 调整代码顺序至 中右左 --> 反转result数组：左右中
    public List<Integer> postorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        stack.push(root);
        //只有栈里没有东西时，才停止循环
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            stack.pop();
            result.add(node.val);
            //注意先push左孩子，因为先进后出，后序遍历要给前序的中左右变成中右左，最后翻转数组
            if(node.left != null) {
                stack.push(node.left);
            } else if (node.right != null) {
                stack.push(node.right);
            }
        }
        //别忘了再把result数组反转过来
        Collections.reverse(result);
        return result;
    }

    /**
     * 中序迭代法遍历，不能再复用前序遍历的代码。
     * 本质原因是因为遍历时的顺序不再是操作的顺序
     * 前序遍历时，从根节点开始，直接对根节点进行操作
     * 而中序遍历先访问左孩子，我们从根开始，要一直找到根节点左孩子的左孩子的左孩子，直到没有
     * 从那个“最左孩子”开始进行操作节点，因此不是遍历一个节点操作一个节点
     */
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curNode = root;
        while(curNode != null || !stack.isEmpty()){
            // 遍历到的节点只要不为空都先压入栈，然后去找他的左孩子
            if(curNode != null){
                stack.push(curNode);
                curNode = curNode.left;
            } else {
                // 当前节点为空时，证明该节点就是最左边的孩子，那么上一个押入栈中的肯定是其父亲节点（前中后的中），直接弹出
                // 并使弹出的节点成为当前节点，这样便于马上去往右孩子找
                curNode = stack.pop();
                result.add(curNode.val);
                // 当前节点为空时，往右孩子去找
                curNode = curNode.right;
            }
        }
        return result;
    }


    /**
     * 统一迭代法，前中后序遍历只需要修改部分代码，可以复用
     * 算法的核心在于，遍历节点时，只要节点不为空，都会在加入该节点之后加入一个空节点（也就是将Null加入栈）
     * 也就是说栈里面中根一定在null的下面，只要遍历到null节点，那么直接找到null的下面一个节点就是前中后的中，这样就可以实现复用代码
     * 因此只需要遍历时,遇到非空节点将遍历的顺序对应到该节点反过来压入栈即可。
     * 遇到空节点弹出后将最上面的节点加入集合，即为遍历结果
     * @param root
     * @return
     */
    //这是前序遍历，因为入栈的顺序是右左中，则出栈顺序时中左右，是前序遍历
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }

}
